Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 93x3sub-boxes of the grid.
The '.' character indicates empty cells.
Example 1:
Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] Explanation: The input board is shown above and the only valid solution is shown below:![]()
Constraints:
board.length == 9board[i].length == 9board[i][j]is a digit or'.'.- It is guaranteed that the input board has only one solution.
Average Rating: 4.25 (40 votes)
Solution
Approach 0: Brute Force
The first idea is to use brut-force
to generate all possible ways to fill the cells
with numbers from 1 to 9,
and then check them to keep the solution only.
That means 981 operations to do,
where 9 is a number of available digits
and 81 is a number of cells to fill.
Hence we're forced to think further how to optimize.
Approach 1: Backtracking
Conceptions to use
There are two programming conceptions here which could help.
The first one is called constrained programming.
That basically means to put restrictions after each number placement. One puts a number on the board and that immediately excludes this number from further usage in the current row, column and sub-box. That propagates constraints and helps to reduce the number of combinations to consider.
The second one called backtracking.
Let's imagine that one has already managed to put several numbers on the board. But the combination chosen is not the optimal one and there is no way to place the further numbers. What to do? To backtrack. That means to come back, to change the previously placed number and try to proceed again. If that would not work either, backtrack again.
How to enumerate sub-boxes
One tip to enumerate sub-boxes: let's use
box_index = (row / 3) * 3 + column / 3where/is an integer division.
Algorithm
Now everything is ready to write down the backtrack function
backtrack(row = 0, col = 0).
-
Start from the upper left cell
row = 0, col = 0. Proceed till the first free cell. -
Iterate over the numbers from
1to9and try to put each numberdin the(row, col)cell.-
If number
dis not yet in the current row, column and box :- Place the
din a(row, col)cell. - Write down that
dis now present in the current row, column and box. - If we're on the last cell
row == 8, col == 8:- That means that we've solved the sudoku.
- Else
- Proceed to place further numbers.
- Backtrack if the solution is not yet here :
remove the last number from the
(row, col)cell.
- Place the
-
Implementation
Complexity Analysis
-
Time complexity is constant here since the board size is fixed and there is no N-parameter to measure. Though let's discuss the number of operations needed : (9!)9. Let's consider one row, i.e. not more than 9 cells to fill. There are not more than 9 possibilities for the first number to put, not more than 9×8 for the second one, not more than 9×8×7 for the third one etc. In total that results in not more than 9! possibilities for a just one row, that means not more than (9!)9 operations in total. Let's compare:
-
981=196627050475552913618075908526912116283103450944214766927315415537966391196809 for the brute force,
-
and (9!)9=109110688415571316480344899355894085582848000000000 for the standard backtracking, i.e. the number of operations is reduced in 1027 times !
-
-
Space complexity : the board size is fixed, and the space is used to store board, rows, columns and boxes structures, each contains
81elements.
November 13, 2019 11:42 AM
Share a simplified version of backtrack solution:
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
n = len(board)
rows, cols, boxes = collections.defaultdict(set), collections.defaultdict(set), collections.defaultdict(set)
for r in range(n):
for c in range(n):
if board[r][c] == '.':
continue
v = int(board[r][c])
rows[r].add(v)
cols[c].add(v)
boxes[(r // 3) * 3 + c // 3].add(v)
def is_valid(r, c, v):
box_id = (r // 3) * 3 + c // 3
return v not in rows[r] and v not in cols[c] and v not in boxes[box_id]
def backtrack(r, c):
if r == n - 1 and c == n:
return True
elif c == n:
c = 0
r += 1
# current grid has been filled
if board[r][c] != '.':
return backtrack(r, c + 1)
box_id = (r // 3) * 3 + c // 3
for v in range(1, n + 1):
if not is_valid(r, c, v):
continue
board[r][c] = str(v)
rows[r].add(v)
cols[c].add(v)
boxes[box_id].add(v)
if backtrack(r, c + 1):
return True
# backtrack
board[r][c] = '.'
rows[r].remove(v)
cols[c].remove(v)
boxes[box_id].remove(v)
return False
backtrack(0, 0)
April 8, 2020 12:38 AM
There's no need creating extra data structure as rows, columns and boxes. It's good for engineering, but not practical for interview. Here's a succint version of backtracing
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
# Check if num can be placed at board[i][j]
def can_place(i, j, num):
# Check row
if any(num == n for n in board[i]):
return False
# Check col
if any(num == n for n in list(zip(*board))[j]):
return False
# Check box
start_row, start_col = (i // 3) * 3, (j // 3) * 3
for r in range(start_row, start_row + 3):
for c in range(start_col, start_col + 3):
if num == board[r][c]:
return False
return True
def find_unassigned():
for r in range(len(board)):
for c in range(len(board[0])):
if board[r][c] == '.':
return r, c
return -1, -1
def solve():
r, c = find_unassigned()
if r == -1 and c == -1:
return True
for num in [str(n) for n in range(1, 10)]:
if can_place(r, c, num):
board[r][c] = num
if solve():
return True
board[r][c] = '.'
return False
if not board:
return
solve()
Last Edit: May 31, 2020 11:31 AM
For simplicity during an interview
Time Complexity: O(9^(m * n))
Space Complexity: O(m*n)
i have three times faster java code(3 ms), what i do is first fill the cells which can only fill one number:
class Solution {
// box size
int n = 3;
// row size
int N = n * n;
int [][] rows = new int[N][N + 1];
int [][] columns = new int[N][N + 1];
int [][] boxes = new int[N][N + 1];
char[][] board;
boolean sudokuSolved = false;
public boolean couldPlace(int d, int row, int col) {
/*
Check if one could place a number d in (row, col) cell
*/
int idx = (row / n ) * n + col / n;
return rows[row][d] + columns[col][d] + boxes[idx][d] == 0;
}
public boolean couldPlaceOnlyOne( int row, int col) {
/*
Check if one could only place one number in (row, col) cell
*/
int place = 0, count = 0;
for (int d = 1; d < 10; d++) {
int idx = (row / n ) * n + col / n;
if (rows[row][d] + columns[col][d] + boxes[idx][d] == 0) {
count += 1;
place = d;
}
}
if (count == 1) {
placeNumber(place, row, col);
}
return false;
}
public void placeNumber(int d, int row, int col) {
/*
Place a number d in (row, col) cell
*/
int idx = (row / n ) * n + col / n;
rows[row][d]++;
columns[col][d]++;
boxes[idx][d]++;
board[row][col] = (char)(d + '0');
}
public void removeNumber(int d, int row, int col) {
/*
Remove a number which didn't lead to a solution
*/
int idx = (row / n ) * n + col / n;
rows[row][d]--;
columns[col][d]--;
boxes[idx][d]--;
board[row][col] = '.';
}
public void placeNextNumbers(int row, int col) {
/*
Call backtrack function in recursion
to continue to place numbers
till the moment we have a solution
*/
// if we're in the last cell
// that means we have the solution
if ((col == N - 1) && (row == N - 1)) {
sudokuSolved = true;
}
// if not yet
else {
// if we're in the end of the row
// go to the next row
if (col == N - 1) backtrack(row + 1, 0);
// go to the next column
else backtrack(row, col + 1);
}
}
public void backtrack(int row, int col) {
/*
Backtracking
*/
// if the cell is empty
if (board[row][col] == '.') {
// iterate over all numbers from 1 to 9
for (int d = 1; d < 10; d++) {
if (couldPlace(d, row, col)) {
placeNumber(d, row, col);
placeNextNumbers(row, col);
// if sudoku is solved, there is no need to backtrack
// since the single unique solution is promised
if (!sudokuSolved) removeNumber(d, row, col);
}
}
} else placeNextNumbers(row, col);
}
public void solveSudoku(char[][] board) {
this.board = board;
// init rows, columns and boxes
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
char num = board[i][j];
if (num != '.') {
int d = Character.getNumericValue(num);
placeNumber(d, i, j);
}
}
}
while (true) {
int flag = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == '.') {
if (couldPlaceOnlyOne(i, j) == true) {
flag = 1;
}
}
}
}
if (flag == 0) {
break;
}
}
backtrack(0, 0);
}
}
why this code only work in python 3 not 2?
Last Edit: August 20, 2020 10:09 PM
I think the operations analysis is wrong. Even the second number has 8 possible candidates, you're still trying to fill from 1-9 for every position. You're not eliminating any number when trying to fill. So I'd say the operation should be 9 ^ (9 * 9)
Clean Python3, dfs by row-based.
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def is_block_valid(i: int, j: int) -> bool:
nums = [board[r][c] for r in range(i-2, i+1) for c in range(j-2, j+1)]
return len(nums) == len(set(nums))
def dfs(i: int, j: int, row: set = None) -> bool:
if i == 9: return True
if j == 9: return dfs(i+1, 0)
if i % 3 == 2 and j % 3 == 2 and not is_block_valid(i, j): return False
if j == 0: row = {str(i) for i in range(1, 10)} - set(board[i])
if board[i][j] != '.': return dfs(i, j+1, row)
if row:
for num in row & cols[j]:
board[i][j] = num
cols[j].discard(num)
row.discard(num)
if dfs(i, j+1, row): return True
cols[j].add(num)
row.add(num)
board[i][j] = '.'
return False
used_cols = [set(row[j] for row in board) for j in range(9)]
cols = [{str(i) for i in range(1, 10)} - nums for nums in used_cols]
dfs(0, 0)
March 28, 2019 6:05 AM
Why two functions are calling each other?
i have three times faster python code(80 ms), what i do is first fill the cells which can only fill one number:
from collections import defaultdict
class Solution:
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
def could_place(d, row, col):
"""
Check if one could place a number d in (row, col) cell
"""
return not (d in rows[row] or d in columns[col] or
d in boxes[box_index(row, col)])
def place_number(d, row, col):
"""
Place a number d in (row, col) cell
"""
rows[row][d] += 1
columns[col][d] += 1
boxes[box_index(row, col)][d] += 1
board[row][col] = str(d)
def remove_number(d, row, col):
"""
Remove a number which didn't lead
to a solution
"""
del rows[row][d]
del columns[col][d]
del boxes[box_index(row, col)][d]
board[row][col] = '.'
def could_place_only_one(row, col):
# if only a number can file in the cell, fill it.
count = []
for d in range(1, 10):
if could_place(d, row, col):
count.append(d)
if len(count) == 1:
place_number(count[0], row, col)
return True
return False
def firstcheck():
while 1:
flag = 0
for i in range(N):
for j in range(N):
if board[i][j] == '.' and could_place_only_one(i, j) == True:
flag = 1
if flag == 0:
break
def place_next_numbers(row, col):
"""
Call backtrack function in recursion
to continue to place numbers
till the moment we have a solution
"""
# if we're in the last cell
# that means we have the solution
if col == N - 1 and row == N - 1:
nonlocal sudoku_solved
sudoku_solved = True
# if not yet
else:
# if we're in the end of the row
# go to the next row
if col == N - 1:
backtrack(row + 1, 0)
# go to the next column
else:
backtrack(row, col + 1)
def backtrack(row=0, col=0):
"""
Backtracking
"""
# if the cell is empty
if board[row][col] == '.':
# iterate over all numbers from 1 to 9
for d in range(1, 10):
if could_place(d, row, col):
place_number(d, row, col)
place_next_numbers(row, col)
# if sudoku is solved, there is no need to backtrack
# since the single unique solution is promised
if not sudoku_solved:
remove_number(d, row, col)
else:
place_next_numbers(row, col)
# box size
n = 3
# row size
N = n * n
# lambda function to compute box index
def box_index(row, col): return (row // n) * n + col // n
# init rows, columns and boxes
rows = [defaultdict(int) for i in range(N)]
columns = [defaultdict(int) for i in range(N)]
boxes = [defaultdict(int) for i in range(N)]
for i in range(N):
for j in range(N):
if board[i][j] != '.':
d = int(board[i][j])
place_number(d, i, j)
sudoku_solved = False
firstcheck()
backtrack()
April 23, 2021 9:54 AM
it also makes sense to precalculate the empty indexes and then using the index for backtracking and not to calculate the next empty index every time
def backtrack(curr_idx)
if curr_idx == len(empty_spaces):
return board
curr_row, curr_col = empty_spaces[curr_idx]
....
for digit in range(1, 10):
board[curr_row][curr_col] = str(digit)
if self.validate_move(board, curr_row, curr_col):
solved = backtrack(curr_idx + 1)
....
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: void solveSudoku(vector<vector<char>>& board) { }};

